package org.example.myleet.p456;

import java.util.TreeMap;

public class Solution2 {

    /**
     * 28 ms
     * 使用TreeMap来维护3的右边的顺序，在log(n)时间内找到比1大比3小的数字，复杂度n*log(n)
     */
    public boolean find132pattern(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return false;
        }
        //使用TreeMap来维护3的右边的顺序，记录key以及频数
        TreeMap<Integer, Integer> rightAll = new TreeMap<>();
        for (int i=2; i<n; ++i) {
            rightAll.put(nums[i], rightAll.getOrDefault(nums[i], 0) + 1);
        }
        //保持min1是3左边最小的数字
        int min1 = nums[0];
        for (int i=1; i<n-1; ++i) {
            min1 = Math.min(min1, nums[i]);
            Integer possible2 = rightAll.ceilingKey(min1+1);
            if (possible2 != null && possible2 < nums[i]) {
                return true;
            }
            //nums[i+1]为3的下一个候选数字
            Integer keyCount = rightAll.get(nums[i+1]);
            if (keyCount == 1) {
                //频数为1时移除该key，因为3移动到下一位时，rightAll管理的数字会减掉这个数字
                rightAll.remove(nums[i+1]);
            } else {
                rightAll.put(nums[i+1], keyCount-1);
            }
        }
        return false;
    }
}
